package com.zk.algorithm.tree;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.Meituan;
import com.zk.algorithm.bean.TreeNode;
import com.zk.algorithm.factory.TreeFactory;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *
 * Given a binary tree, return the zigzag level order traversal of its nodes' values.
 * (ie, from left to right, then right to left for the next level and alternate between).
 *
 * 左 --> 右
 * 左 <-- 右
 *
 * @author zk
 */
@Meituan("https://www.nowcoder.com/discuss/151829?type=2&order=0&pos=48&page=1")
public class BinaryTreeZigzagLevelOrderTraversal {

    // ====================
    // 但其实当前位于第几层，完全可以使用 queue.size() 来确定
    //           3
    //          / \
    //         9  20
    //           /  \
    //          15   7
    // ====================

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> wrapList = new LinkedList<List<Integer>>();

        if (root == null) return wrapList;

        queue.offer(root);
        boolean left2Right = true;

        while (!queue.isEmpty()) {
            // [3] => 1
            // [9, 20] => 2
            // [15, 17] => 2
            int levelNum = queue.size();
            List<Integer> subList = new LinkedList<Integer>();

            for (int i = 0; i < levelNum; i++) {
                TreeNode cur = queue.poll();

                if (left2Right) {
                    subList.add(cur.val);
                } else {
                    subList.add(0, cur.val);
                }

                if (cur.left != null)
                    queue.offer(cur.left);

                if (cur.right != null)
                    queue.offer(cur.right);
            }

            wrapList.add(subList);
            left2Right = !left2Right;
        }

        return wrapList;
    }

    public static void main(String...args) {
        List<List<Integer>> result = new BinaryTreeZigzagLevelOrderTraversal().zigzagLevelOrder(TreeFactory.buildTree(new int[] {
                1,2,3,4,5,6,7,8,9,10
        }));

        Utils.println(result);
    }

}
